#define  _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <vector>

void BubbleSort(vector<int>& v)
{
	int n = v.size();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (v[j] > v[j + 1])
				swap(v[j], v[j + 1]);
		}
	}
}

void SelectSort(vector<int>& v)
{
	int begin = 0, end = v.size() - 1;
	while (begin < end)
	{
		int fmin = begin, fmax = begin;
		for (int i = begin; i <= end; i++)
		{
			if (v[i] > v[fmax]) fmax = i;
			if (v[i] < v[fmin]) fmin = i;
		}
		swap(v[begin], v[fmin]);
		if (begin == fmax) fmax = fmin;
		swap(v[end], v[fmax]);
		begin++;
		end--;
	}
}

void InsertSort(vector<int>& v)
{
	int n = v.size();
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = v[end + 1];
		while (end >= 0)
		{
			if (v[end] > tmp)
			{
				v[end + 1] = v[end];
				end--;
			}
			else
				break;
		}
		v[end + 1] = tmp;
	}
}

void QuickSort(vector<int>& a, int left, int right)
{
	if (left >= right) return;
	int key = a[left + (rand() % (right - left + 1))];
	int begin = left - 1, end = right + 1;
	int curr = left;
	while (curr < end)
	{
		if (a[curr] < key) swap(a[++begin], a[curr++]);
		else if (a[curr] == key) curr++;
		else swap(a[--end], a[curr]);
	}
	//[0, begin][begin + 1, end - 1][end, n]
	QuickSort(a, left, begin);
	QuickSort(a, end, right);
}


void MergeSort(vector<int>& a, int left, int right, vector<int>& tmp)
{
	if (left >= right) return;
	int mid = left + (right - left) / 2;
	MergeSort(a, left, mid, tmp);
	MergeSort(a, mid + 1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int curr = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			tmp[curr++] = a[begin1++];
		else
			tmp[curr++] = a[begin2++];
	}
	while (begin1 <= end1)
		tmp[curr++] = a[begin1++];
	while (begin2 <= end2)
		tmp[curr++] = a[begin2++];
	for (int i = left; i <= right; i++)
		a[i] = tmp[i];
}

void ShellSort(vector<int>& v)
{
	int n = v.size();
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = v[end + gap];
			while (end >= 0)
			{
				if (v[end] > tmp)
				{
					v[end + gap] = v[end];
					end -= gap;
				}
				else
					break;
			}
			v[end + gap] = tmp;
		}
	}
}

int main()
{
	vector<int> v{ 9, 4, 3, 6, 1, 0, 5, 7, 2, 8, 2, 2, 2, 3, 1, 5, 8, 9, 4, 1, 3, 3, 9, 9, 9 };
	vector<int> tmp(v.size());
	ShellSort(v);
	for (auto e : v)
		cout << e << ' ';
	cout << endl;
	return 0;
}